1. Technical Field of the Invention
This invention relates to a method and system for managing shared resources, and more particularly to a stationary queue for managing access to scarce or serially reusable resources by multiple process threads.
2. Background Art
Hardware device drivers that support multi-tasking operating systems must cope with the challenge of managing simultaneous access to scarce or serially re-useable resources by multiple program entities, also referred to as process threads.
When a thread requests access to a resource that is unavailable, and outright rejection of the request is not allowed, the thread must be suspended until the resource becomes available (is freed by whatever other process is currently using it). Fairness is usually important. That is, requests for the resource should be honored in the order in which they were received.
Solutions to this problem are plentiful, but involve manipulating data structures such as first in first out (FIFOs) buffers or linked lists for managing the queuing of requests and honoring them in the order in which the occur. Such approaches are often unnecessarily complex or wasteful of either CPU cycles or memory (or both) for certain classes of this problem.
Thus, the problem of resource management has typically been solved in one of two ways: (1) free-for-all waking of any and all threads waiting for the scarce resource; or, (2) maintaining a queue structure, typically in the form of a linked list or a FIFO, to enforce order and to enable waking one thread at a time.
If multiple threads are all awakened when a single resource instance becomes available, then only one thread will be satisfied and the others will have to go to sleep (wait) again. This causes excessive churn on the system's process (or thread) run queue. Further, the free-for-all waking of all threads at once does nothing to enforce “fairness”. There is, consequently, a need in the art for a method and system which is more efficiently uses system CPU resources.
In order to maintain any form of linked list structure (the classical method of queuing objects of any sort) or a first in first out (FIFO) buffer, ancillary structures must be consulted or additional memory references made in order to create the wake-up ID for the next thread in line. This requires both resources and time. There is, consequently, a need in the art for a method and system which are far faster and use less memory.
It is an object of the invention to efficiently share a scarce resource among multiple program entities (threads), and to do so with minimal CPU usage and negligible memory overhead.
It is a further object of the invention to wake waiting threads, one at time, in the exact order in which they began waiting for the resource, while minimizing system churn and guaranteeing fairness.
It is a further object of the invention to manage such resources by maintaining two counters, wherein the counters themselves not only indicate the presence (and number) of waiting threads, but contain all information necessary to wake the threads in order, one at a time.